import java.util.*;

public class Traversal {
    /**
     * 二叉树遍历，前序/中序/后序递归遍历
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     * 前序遍历
     */
    public int[] preorderTraversal (TreeNode root) {
        ArrayList<Integer> resList = new ArrayList<>();
        preHelper(root, resList);

        int[] res = new int[resList.size()];
        for (int i = 0; i < resList.size(); ++i) {
            res[i] = resList.get(i);
        }
        return res;
    }

    private void preHelper(TreeNode root, ArrayList<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preHelper(root.left, res);
        preHelper(root.right, res);
    }

    /**
     * 中序遍历
     */
    public int[] inorderTraversal (TreeNode root) {
        ArrayList<Integer> resList = new ArrayList<>();
        midHelper(root, resList);

        int[] res = new int[resList.size()];
        for (int i = 0; i < resList.size(); ++i) {
            res[i] = resList.get(i);
        }
        return res;
    }

    private void midHelper(TreeNode root, ArrayList<Integer> res) {
        if (root == null) {
            return;
        }
        midHelper(root.left, res);
        res.add(root.val);
        midHelper(root.right, res);
    }

    /**
     * 后序遍历
     */
    public int[] postorderTraversal (TreeNode root) {
        ArrayList<Integer> resList = new ArrayList<>();
        postHelper(root, resList);

        int[] res = new int[resList.size()];
        for (int i = 0; i < resList.size(); ++i) {
            res[i] = resList.get(i);
        }
        return res;
    }

    private void postHelper(TreeNode root, ArrayList<Integer> res) {
        if (root == null) {
            return;
        }
        postHelper(root.left, res);
        postHelper(root.right, res);
        res.add(root.val);
    }
}